package dataStructures.impl;

import dataStructures.ISearchTree;

/**
 * Binary Tree implementation of {@link ISearchTree}.
 * 
 * This implementation assumes that each binary tree node has access to its
 * parent as well.
 * 
 * @author Vikas Bahirwani
 */
public class BinarySearchTree implements ISearchTree {

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#search(java.lang.Object, int)
	 */
	@Override
	public Object search(Object root, int key) {
		if (root == null || ((BinaryTreeNode) root).getKey() == key) {
			return root;
		} else {
			BinaryTreeNode node = (BinaryTreeNode) root;
			if (key < node.getKey()) {
				return search(node.getLeftChild(), key);
			} else {
				return search(node.getRightChild(), key);
			}

		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#minimum(java.lang.Object)
	 */
	@Override
	public Object minimum(Object root) {
		if (root == null) {
			return root;
		}

		BinaryTreeNode node = (BinaryTreeNode) root;
		while (node.getLeftChild() != null) {
			node = node.getLeftChild();
		}
		return node;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#maximum(java.lang.Object)
	 */
	@Override
	public Object maximum(Object root) {
		if (root == null) {
			return root;
		}

		BinaryTreeNode node = (BinaryTreeNode) root;
		while (node.getRightChild() != null) {
			node = node.getRightChild();
		}
		return node;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#inorderTreeWalk(java.lang.Object)
	 */
	@Override
	public void inorderTreeWalk(Object root) {
		if (root != null) {
			BinaryTreeNode node = (BinaryTreeNode) root;
			inorderTreeWalk(node.getLeftChild());
			System.out.println(node);
			inorderTreeWalk(node.getRightChild());
		}

	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#preorderTreeWalk(java.lang.Object)
	 */
	@Override
	public void preorderTreeWalk(Object root) {
		if (root != null) {
			BinaryTreeNode node = (BinaryTreeNode) root;
			System.out.println(node);
			preorderTreeWalk(node.getLeftChild());
			preorderTreeWalk(node.getRightChild());

		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#postorderTreeWalk(java.lang.Object)
	 */
	@Override
	public void postorderTreeWalk(Object root) {
		if (root != null) {
			BinaryTreeNode node = (BinaryTreeNode) root;
			postorderTreeWalk(node.getLeftChild());
			postorderTreeWalk(node.getRightChild());
			System.out.println(node);
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#successor(java.lang.Object)
	 */
	@Override
	public Object successor(Object node) {
		if (node == null) {
			return null;
		}

		BinaryTreeNode bstNode = (BinaryTreeNode) node;
		if (bstNode.getRightChild() != null) {
			return minimum(bstNode.getRightChild());
		} else {
			BinaryTreeNode parent = bstNode.getParent();
			while (parent != null && parent.getRightChild() == bstNode) {
				bstNode = parent;
				parent = bstNode.getParent();
			}

			return parent;

		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#predecessor(java.lang.Object)
	 */
	@Override
	public Object predecessor(Object node) {
		if (node == null) {
			return null;
		}

		BinaryTreeNode bstNode = (BinaryTreeNode) node;
		if (bstNode.getLeftChild() != null) {
			return maximum(bstNode.getLeftChild());
		} else {
			BinaryTreeNode parent = bstNode.getParent();
			while (parent != null && bstNode == parent.getLeftChild()) {
				bstNode = parent;
				parent = bstNode.getParent();
			}
			return parent;
		}

	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#insert(java.lang.Object,
	 * java.lang.Object)
	 */
	@Override
	public Object insert(Object root, Object newNode) {
		if (root == null) {
			return newNode;
		}

		BinaryTreeNode next = (BinaryTreeNode) root;
		BinaryTreeNode newBSTNode = (BinaryTreeNode) newNode;
		BinaryTreeNode parent = null;
		while (next != null) {
			parent = next;
			if (newBSTNode.getKey() < parent.getKey()) {
				next = parent.getLeftChild();
			} else {
				next = parent.getRightChild();
			}
		}

		newBSTNode.setParent(parent);
		if (newBSTNode.getKey() < parent.getKey()) {
			parent.setLeftChild(newBSTNode);
		} else {
			parent.setRightChild(newBSTNode);
		}

		return root;

	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.ISearchTree#delete(java.lang.Object,
	 * java.lang.Object)
	 */
	@Override
	public Object delete(Object root, Object node) {
		BinaryTreeNode bstNode = (BinaryTreeNode) node;
		BinaryTreeNode nodeToDelete;

		if (bstNode.getLeftChild() == null || bstNode.getRightChild() == null) {
			nodeToDelete = bstNode;
		} else {
			nodeToDelete = (BinaryTreeNode) successor(bstNode);
		}

		BinaryTreeNode child = null;
		if (nodeToDelete.getLeftChild() != null) {
			child = nodeToDelete.getLeftChild();
		} else {
			child = nodeToDelete.getRightChild();
		}

		if (child != null) {
			child.setParent(nodeToDelete.getParent());
		}

		if (nodeToDelete.getParent() == null) {
			// child is the new root
			return child;
		} else {
			if (nodeToDelete.getParent().getLeftChild() == nodeToDelete) {
				nodeToDelete.getParent().setLeftChild(child);
			} else {
				nodeToDelete.getParent().setRightChild(child);
			}
		}

		if (nodeToDelete != bstNode) {
			bstNode.setKey(nodeToDelete.getKey());
			bstNode.setData(nodeToDelete.getData());
		}

		return root;
	}

	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		BinaryTreeNode root = (BinaryTreeNode) tree.insert(null,
				new BinaryTreeNode(50, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(30, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(70, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(20, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(40, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(10, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(25, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(45, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(60, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(80, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(55, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(65, null));
		root = (BinaryTreeNode) tree.insert(root, new BinaryTreeNode(75, null));

		tree.inorderTreeWalk(root);
		System.out.println("---");
		tree.preorderTreeWalk(root);
		System.out.println("---");
		tree.postorderTreeWalk(root);
		System.out.println("---");

		System.out.println(tree.minimum(root));
		System.out.println(tree.maximum(root));
		System.out.println(tree.predecessor(root));
		System.out.println(tree.successor(root));

		System.out.println("Searching for the node 65");
		BinaryTreeNode node = (BinaryTreeNode) tree.search(root, 65);
		System.out.println("Successor of 65 is " + tree.successor(node));
		tree.delete(root, node);
		System.out.println("Deleting node 65");
		tree.inorderTreeWalk(root);
		System.out.println("---");

		System.out.println("Searching for the node 55");
		node = (BinaryTreeNode) tree.search(root, 55);
		System.out.println("Successor of 55 is " + tree.successor(node));
		System.out.println("Predecessor of 55 is " + tree.predecessor(node));

		System.out.println("Searching for the node 40");
		node = (BinaryTreeNode) tree.search(root, 40);
		System.out.println("Successor of 40 is " + tree.successor(node));
		System.out.println("Predecessor of 40 is " + tree.predecessor(node));
		tree.delete(root, node);
		System.out.println("Deleting node 40");
		tree.inorderTreeWalk(root);
		System.out.println("---");

		System.out.println("Searching for the node 80");
		node = (BinaryTreeNode) tree.search(root, 80);
		tree.delete(root, node);
		System.out.println("Deleting node 80");
		tree.inorderTreeWalk(root);
		System.out.println("---");

		System.out.println("Searching for the node 20");
		node = (BinaryTreeNode) tree.search(root, 20);
		tree.delete(root, node);
		System.out.println("Deleting node 20");
		tree.inorderTreeWalk(root);
		System.out.println("---");

		System.out.println("Searching for the node 50");
		node = (BinaryTreeNode) tree.search(root, 50);
		tree.delete(root, node);
		System.out.println("Deleting node 50");
		tree.inorderTreeWalk(root);
		System.out.println("---");
		
		tree.preorderTreeWalk(root);
		System.out.println("---");
		tree.postorderTreeWalk(root);

	}

}
